package leetcode.graph.bfs.p773;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 
 * @Title: Solution_v1.java 
 * @Package leetcode.graph.bfs.p773 
 * @Description: 773. 滑动谜题
 *                  将二维数组构成的面板解析为一个字符串（参考题解）
 * @author CandyWall   
 * @date 2021年1月18日 下午3:57:54 
 * @version V1.0
 */
class Solution_v3 {
    public int slidingPuzzle(int[][] board) {
        String initalState = boardToString(board);
        if(initalState.equals("123450")) {
            return 0;
        }
        HashMap<String, Integer> visited = new HashMap<>();
        Queue<String> queue = new LinkedList<>();
        queue.add(initalState);
        visited.put(initalState, 0);
        while(!queue.isEmpty()) {
            String curState = queue.remove();
            for(String nextState : nextStates(curState)) {
                if(!visited.containsKey(nextState)) {
                    queue.add(nextState);
                    visited.put(nextState, visited.get(curState) + 1);
                    // 如果结果是123450，就结束搜索，返回移动次数
                    if(nextState.equals("123450")) {
                        return visited.get(nextState);
                    }
                }
            }
        }
        
        return -1;
    }
    
    // 根据当前面板上面的数字序列滑动一次后可能出现的数字数列
    private ArrayList<String> nextStates(String num) {
        ArrayList<String> res = new ArrayList<>();
        int[][] board = stringToBoard(num);
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 3; j++) {
                // 找到面板中0的位置
                if(board[i][j] == 0) {
                    // 跟其他位置交换
                    int[][] dirs = {{0, -1}, {1, 0}, {0, 1} ,{-1, 0}};
                    for(int d = 0; d < 4; d++) {
                        int nextI = i + dirs[d][0];
                        int nextJ = j + dirs[d][1];
                        if(inArea(nextI, nextJ)) {
                            // 交换两个位置的元素
                            swap(board, i, j, nextI, nextJ);
                            // 记录交换后的结果
                            res.add(boardToString(board));
                            // 面板复位，为寻找下一种可能性做准备
                            swap(board, i, j, nextI, nextJ);
                        }
                    }
                    break;
                }
            }
        }
        return res;
    }
    
    // 交换数组中的两个元素
    private void swap(int[][] board, int i, int j, int nextI, int nextJ) {
        int temp = board[i][j];
        board[i][j] = board[nextI][nextJ];
        board[nextI][nextJ] = temp;
    }

    // 判断二维数组的索引是否合法
    private boolean inArea(int x, int y) {
        return x >= 0 && x < 2 && y >= 0 && y < 3;
    }

    // 将当前整型数字转成6位数字的面板
    private int[][] stringToBoard(String num) {
        int[][] board = new int[2][3];
        for(int k = 0; k < 6; k++) {
            int i = k / 3, j = k % 3;
            board[i][j] = num.charAt(k) - '0';
        }
        return board;
    }

    // 将包含6个数字的面板转成一个6位的整型数字
    private String boardToString(int[][] board) {
        StringBuilder sb = new StringBuilder();
        for(int k = 0; k < 6; k++) {
            int i = k / 3, j = k % 3;
            sb.append(board[i][j]);
        }
        return sb.toString();
    }
    
    public static void main(String[] args) {
        System.out.println(new Solution_v3().boardToString(new int[][] {{1, 2, 3}, {5, 4, 0}}));
        int[][] board = new Solution_v3().stringToBoard("123540");
        for(int i = 0; i < 2; i++) {
            for(int j = 0; j < 3; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
        System.out.println(new Solution_v3().slidingPuzzle((new int[][] {{1, 2, 3}, {5, 4, 0}})));
        System.out.println(new Solution_v3().slidingPuzzle((new int[][] {{1, 2, 3}, {4, 0, 5}})));
        System.out.println(new Solution_v3().slidingPuzzle((new int[][] {{4, 1, 2}, {5, 0, 3}})));
        System.out.println(new Solution_v3().slidingPuzzle((new int[][] {{1, 2, 3}, {4, 5, 0}})));
    }
}